using System;
using System.Collections.Generic;
using System.Text;

namespace MyClever.Lib
{
    class Node<T>
    {
        public T data;
        public List<T> edgesTo;

        public Node(T data, List<T> edge)
        {
            this.data = data;
            this.edgesTo = edge;
        }

        // Get a string representation of the node
        public override String ToString()
        {
            return this.data.ToString();
        }
    }

    // todo: muss alles noch getestet werden!!
    // bisher habe ich alles nur mit strings gemacht


    // This class uses the topological sorting algorithm.
    // You can get more informations here:
    //  * http://en.wikipedia.org/wiki/Topological_sorting
    //  * http://www-i1.informatik.rwth-aachen.de/~algorithmus/algo8.php
    //  * http://de.wikipedia.org/wiki/Topologische_Sortierung

    //PSEUDO-CODE:
    //L - Empty list that will contain the sorted elements
    //S - Set of all nodes with no incoming edges
    //while S is non-empty do
    //    remove a node n from S
    //    insert n into L
    //    for each node m with an edge e from n to m do
    //        remove edge e from the graph
    //        if m has no other incoming edges then
    //            insert m into S
    //if graph has edges then
    //    output error message (graph has at least one cycle)
    //else 
    //    output message (proposed topologically sorted order: L)
    class TopologicalSorting<T>
    {
        private List<Node<T>> graph;
        
        public TopologicalSorting(ref List<Node<T>> toSort, out Queue<Node<T>> L)
        {
            graph = toSort;

            L = new Queue<Node<T>>();

            Queue<Node<T>> S;
            this.GetAllNodesWithoutEdges(out S);

            while (S.Count > 0)
            {
                Node<T> nodeOn = S.Dequeue();
                L.Enqueue(nodeOn);

                List<Node<T>> dependentNodes;
                this.GetAllDependentNodes(nodeOn, out dependentNodes);

                foreach (Node<T> dependentNodeOn in dependentNodes)
                {
                    this.RemoveEdge(dependentNodeOn, nodeOn.data);

                    if (dependentNodeOn.edgesTo.Count == 0)
                    {
                        S.Enqueue(dependentNodeOn);
                    }
                }

            }

            if (this.NumOpenEdges() > 0)
            {
                L = null;
            }
        }

        private void GetAllNodesWithoutEdges(out Queue<Node<T>> S)
        {
            S = new Queue<Node<T>>();

            foreach (Node<T> nodeOn in graph)
            {
                if (nodeOn.edgesTo.Count == 0)
                {
                    S.Enqueue(nodeOn);
                }
            }
        }

        private void GetAllDependentNodes(Node<T> dependingFrom, out List<Node<T>> dependentNodes)
        {
            dependentNodes = new List<Node<T>>();
            
            foreach (Node<T> nodeOn in graph)
            {
                foreach (T edgeOn in nodeOn.edgesTo)
                {
                    // todo<. gibt es keinen besseren weg als gegen string zu testen?
                    if (edgeOn.ToString() == dependingFrom.data.ToString())
                    {
                        dependentNodes.Add(nodeOn);
                    }
                }
            }
        }

        private void RemoveEdge(Node<T> toEdit, T toDelete)
        {
            toEdit.edgesTo.Remove(toDelete);
        }

        private int NumOpenEdges()
        {
            int numOpenEdges = 0;

            foreach (Node<T> nodeOn in graph)
            {
                numOpenEdges += nodeOn.edgesTo.Count;
            }
            return numOpenEdges;
        }
    }
}
